#include "graph.h"
#define ll long long
#define eb emplace_back
#define ep emplace
#define pii pair<int,int>
#define fi first
#define se second
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define mems(arr,x) memset(arr,x,sizeof(arr))
#define memc(arr1,arr2) memcpy(arr1,arr2,sizeof(arr2))
using namespace std;
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int maxn=1010;
int mp[maxn][maxn],son[maxn][maxn],dd[maxn][maxn],dep[maxn],fa[maxn],deg[maxn];
int dp[maxn][maxn];
bool vis[maxn],up[maxn][maxn];
int n;
inline int id(int u){return u;}
int dfs_tree(){
    int c=Color();
    if(c^1){Move(LastRoad(),c);return 0;}
    int u=++n;
    c=2;
    int d=NumberOfRoads(),fr=LastRoad();
    for(int i=1;i<=d;i++){
        Move(i,c);
        int t=dfs_tree();
        if(t)   mp[u][t]=i,son[u][i]=t;  // tree edge
        else    up[u][i]=true;  // grandfather edge
    }
    if(u^1) Move(fr,c);
    return u;
}
void dfs(int u,int col,int x,int y){
    int d=NumberOfRoads(),fr=LastRoad();
    deg[u]=d;
    int nx=x,nc=col;
    nx++;if(nx>y)nx=1,nc=nc%3+1;
    for(int i=1;i<=d;i++){
        if(up[u][i]){
            Move(i,col);
            int ct=Color();
            Move(LastRoad(),ct);
            ct--;
            dd[u][i]+=ct*y;
        }
        else{
            int t=son[u][i];
            dep[t]=dep[u]+1;
            fa[t]=u;
            Move(i,col);
            dfs(t,nc,nx,y);
        }
    }
    if(u^1) Move(fr,col);
}
inline void getmn(int &x,int y){(x>y)&&(x=y);}
int ans[maxn];
void floyd(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(mp[i][j])    dp[i][j]=dp[j][i]=1; 
            else if(i==j)   dp[i][j]=0;
            else    dp[i][j]=1e9;
        }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)   getmn(dp[i][j],dp[i][k]+dp[k][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)if(dp[i][j]<=n)    ans[dp[i][j]]++;
}
void Inspect(int R) {
    dfs_tree();
    for(int i=1,s=1;i<=5;i++,s*=3)  dfs(1,1,1,s);
    for(int u=1;u<=n;u++){
        for(int i=1;i<=deg[u];i++){
            if(up[u][i]&&dep[u]>dd[u][i]){
                // debug("%d %d %d %d\n",u,i,dep[u],dd[u][i]);
                int jd=dep[u]-dd[u][i],p=u;
                while(jd--) p=fa[p];
                mp[u][p]=1;
            }
        }
    }
    floyd();
    for(int i=1;i<=R;i++)   Answer(i,ans[i]>>1);
}